//给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 
//
// 例如： 
//给定二叉树 [3,9,20,null,null,15,7], 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7
// 
//
// 返回锯齿形层次遍历如下： 
//
// [
//  [3],
//  [20,9],
//  [15,7]
//]
// 
// Related Topics 栈 树 广度优先搜索 
// 👍 238 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

import java.util.*;

/**
 * Java：二叉树的锯齿形层次遍历
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P103_BinaryTreeZigzagLevelOrderTraversal {
    public static void main(String[] args) {
        Solution solution = new P103_BinaryTreeZigzagLevelOrderTraversal().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 有点费时的写法
     */
    //class Solution {
    //    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    //        List<List<Integer>> res = new ArrayList<>();
    //        if (root == null) {
    //            return res;
    //        }
    //        Deque<TreeNode> deque = new ArrayDeque<>();
    //        deque.push(root);
    //        // true-先左 false-先右
    //        boolean sort = true;
    //        while (!deque.isEmpty()) {
    //            // 临时存放每层的node
    //            List<TreeNode> treeNodeList = new ArrayList<>(deque.size());
    //            while (!deque.isEmpty()) {
    //                treeNodeList.add(deque.pop());
    //            }
    //            List<Integer> tempValList = new ArrayList<>(treeNodeList.size());
    //            for (TreeNode treeNode : treeNodeList) {
    //                tempValList.add(treeNode.val);
    //                if (sort) {
    //                    if(treeNode.left != null) {
    //                        deque.push(treeNode.left);
    //                    }
    //                    if(treeNode.right != null) {
    //                        deque.push(treeNode.right);
    //                    }
    //                } else {
    //                    if(treeNode.right != null) {
    //                        deque.push(treeNode.right);
    //                    }
    //                    if(treeNode.left != null) {
    //                        deque.push(treeNode.left);
    //                    }
    //                }
    //            }
    //            sort = !sort;
    //            res.add(tempValList);
    //        }
    //        return res;
    //    }
    //}

    /**
     * 简洁写法， 判断是否头插还是尾插
     */
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) {
                return result;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            // 记录是否反转
            boolean isReverse = false;
            while (!queue.isEmpty()) {
                LinkedList<Integer> oneLevel = new LinkedList<>();
                // 每次都取出一层的所有数据
                int count = queue.size();
                for (int i = 0; i < count; i++) {
                    TreeNode node = queue.poll();
                    if (!isReverse) {
                        oneLevel.add(node.val);
                    } else {
                        oneLevel.addFirst(node.val);
                    }
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                isReverse = !isReverse;
                result.add(oneLevel);
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
